Exercise (Week 5)
Table of Contents
DUE: Sun 8 April 23:59:59
1 Getting Started
Download the exercise tarball and extract it to a directory in your
home directory at CSE. This tarball contains a file, called Ex03.hs,
wherein you will do all of your programming.
To test your code, run the following shell commands to open a GHCi session:
$ 3141
newclass starting new subshell for class COMP3141...
$ cabal repl
Resolving dependencies...
Configuring Ex03-1.0...
Preprocessing executable 'Ex03' for Ex03-1.0..
GHCi, version 8.2.2: http://www.haskell.org/ghc/ :? for help
[1 of 1] Compiling Ex03 (Ex03.hs, interpreted)
Ok, one module loaded.
*Ex03> quickCheck prop_mysteryPred_1
...
Calling quickCheck in the above way will run the given QuickCheck property
with 100 random test cases.
Note that you will only need to submit Ex03.hs, so only make changes
to that file.
Download the exercise tarball and extract it to a directory on
your local machine. This tarball contains a file, called Ex03.hs,
wherein you will do all of your programming.
To test your code, run the following shell commands to open a GHCi session:
$ stack repl
Configuring GHCi with the following packages: Ex03
Using main module: 1. Package 'Ex03' component exe:Ex03 ...
GHCi, version 8.2.2: http://www.haskell.org/ghc/ :? for help
[1 of 1] Compiling Ex03 (Ex03.hs, interpreted)
Ok, one module loaded.
*Ex03> quickCheck prop_mysteryPred_1
...
Calling quickCheck in the above way will run the given QuickCheck property
with 100 random test cases.
Note that you will only need to submit Ex03.hs, so only make changes
to that file.
Download the Haskell for Mac project and unzip it somewhere on your
local machine. Open the project in Haskell for Mac, and begin
coding in Ex03.hs.
The quickcheck tests have already been placed into the playground
for Ex03.hs, so that Haskell for Mac will automatically rerun
tests every time you update your code.
Note that you will only need to submit Ex03.hs, so only make changes
to that file.
2 QuickCheck and Search Trees
The file Ex03.hs includes the support code described in the following as well as stubs for the three functions that you must implement.
The QuickCheck properties discussed below are also included.
We include a binary tree implementation, plus a predicate, isBST, which returns True
if a tree is a binary search tree (that is, an infix traversal of the tree is sorted).
data BinaryTree = Branch Integer BinaryTree BinaryTree | Leaf deriving (Show, Ord, Eq) isBST :: BinaryTree -> Bool isBST Leaf = True isBST (Branch v l r) = and [ allTree (< v) l, allTree (>= v) r , isBST l, isBST r ] where allTree :: (Integer -> Bool) -> BinaryTree -> Bool allTree f (Branch v l r) = f v && allTree f l && allTree f r allTree f (Leaf) = True
We also include insert and deleteAll functions for binary search trees:
-- Add an integer to a BinaryTree, preserving BST property. insert :: Integer -> BinaryTree -> BinaryTree
-- Remove all instances of an integer in a binary tree, -- preserving BST property deleteAll :: Integer -> BinaryTree -> BinaryTree
An arbitrary generator that generates binary search trees:
searchTrees :: Gen BinaryTree
If we wanted to check our generator, we can check it by running the additional property:
prop_searchTrees = forAll searchTrees isBST
We use the arbitrary search tree generator rather than prefix our properties with a guard like isBST tree ==>
to prevent QuickCheck generating lots of spurious test cases.
2.1 Implementing A Mystery Function (Part 1a, 2 Mark)
Write a predicate function mysteryPred, which has the following type signature:
mysteryPred :: Integer -> BinaryTree -> Bool
It must satisfy the following QuickCheck properties:
prop_mysteryPred_1 integer = forAll searchTrees $ \tree -> mysteryPred integer (insert integer tree) prop_mysteryPred_2 integer = forAll searchTrees $ \tree -> not (mysteryPred integer (deleteAll integer tree))
You can test your mysteryPred implementation by simply running quickCheck prop_mysteryPred_[1-2] in the playground or GHCi.
2.2 Even more mysterious (Part 1b, 3 Marks)
Write a function mysterious, with the following type signature:
mysterious :: BinaryTree -> [Integer]
It must satisfy the following QuickCheck properties:
prop_mysterious_1 integer = forAll searchTrees $ \tree -> mysteryPred integer tree == (integer `elem` mysterious tree) prop_mysterious_2 = forAll searchTrees $ isSorted . mysterious isSorted :: [Integer] -> Bool isSorted (x:y:rest) = x <= y && isSorted (y:rest) isSorted _ = True
You can test your mysterious implementation by simply running quickCheck prop_mysterious_[1-2] in a playground or GHCi.
2.3 Balancing Act (Part 2, 4 Marks)
First, we have the generator:
sortedListsWithoutDuplicates :: Gen [Integer]
We use a generator to produce sortedListsWithoutDuplicates because guarding our properties with isSorted list ==> etc.
means that QuickCheck will waste a lot of time randomly generating lists and checking if they satisfy the guard.
We can check if our generator works with the following properties:
prop_sortedListsWithoutDuplicates_1 = forAll sortedListsWithoutDuplicates isSorted prop_sortedListsWithoutDuplicates_2 = forAll sortedListsWithoutDuplicates $ \x -> x == nub x
Write a function astonishing, of type [Integer] -> BinaryTree that satisfies these properties:
prop_astonishing_1 = forAll sortedListsWithoutDuplicates $ isBST . astonishing prop_astonishing_2 = forAll sortedListsWithoutDuplicates $ isBalanced . astonishing prop_astonishing_3 = forAll sortedListsWithoutDuplicates $ \ integers -> mysterious (astonishing integers) == integers
Where isBalanced is a predicate that returns true if a tree is height-balanced:
isBalanced :: BinaryTree -> Bool isBalanced Leaf = True isBalanced (Branch v l r) = and [ abs (height l - height r) <= 1 , isBalanced l , isBalanced r ] where height Leaf = 0 height (Branch v l r) = 1 + max (height l) (height r)
Note: This definition of isBalanced is a rather generous definition of balanced trees.
Can you find an example of a tree that is not very balanced for which this function would still return True?
What would a stricter predicate look like?
3 Submission instructions
You can submit your exercise by typing:
$ give cs3141 Ex03 Ex03.hs
on a CSE terminal, or by using the give web interface. Your file must be named Ex03.hs (case-sensitive!).
A dry-run test will partially autotest your solution at submission time. To get full marks, you will need to
perform further testing yourself.